package com.ls.eightSort;

import static com.ls.eightSort.QuickSort.swap;

/**
 * 插入排序
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] arr= {4,5,65,3,2,1,66};
        show(arr);
        sort(arr);
        show(arr);
    }


    /**
     * 插入排序
     */
    public static void sort(int arr[]){
        // n个元素，确定n-1个元素的位置就行
        for (int i = 1; i < arr.length; i++) {
            // 使用视频讲的while循环,不用自己手动break了
            // 待插入值
            int insertValue = arr[i];
            // 插入的索引
            int j = i-1;
            while (j>=0 && insertValue<arr[j]){
                // 后移
                arr[j+1] = arr[j];
                // j就是需要插入的前一个位置
                j--;
            }
            // 移出来的位置插入进去
            arr[j+1] = insertValue;
        }
    }

    public static void show(int arr[]){
        for (int i : arr) {
            System.out.print(i+",");
        }
        System.out.println();
    }
}
